package com.chj.chuji.tijie06;

public class TreeToSequence {
	public static class Node {
		int val = 0;
		Node left = null;
		Node right = null;

		public Node(int val) {
			this.val = val;
		}
	}

	public static String toSequence(Node head) {
		if (head == null) {
			return "";
		}
		String res = head.val + "";
		res += head.left != null ? "(" : "";
		res += toSequence(head.left);
		res += toSequence(head.right);
		res += head.right != null ? ")" : "";
		return res;
	}

	public static String serialByPre(Node head) {
		if (head == null) {
			return "#!";
		}
		String res = head.val + "!";
		res += serialByPre(head.left);
		res += serialByPre(head.right);
		return res;
	}

	// for test -- print tree
	public static void printTree(Node head) {
		System.out.println("Binary Tree:");
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	public static void printInOrder(Node head, int height, String to, int len) {
		if (head == null) {
			return;
		}
		printInOrder(head.right, height + 1, "v", len);
		String val = to + head.val + to;
		int lenM = val.length();
		int lenL = (len - lenM) / 2;
		int lenR = len - lenM - lenL;
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);
		printInOrder(head.left, height + 1, "^", len);
	}

	public static String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
			buf.append(space);
		}
		return buf.toString();
	}

	public static void main(String[] args) {
		Node head1 = new Node(1);
		head1.left = new Node(2);
		head1.right = new Node(3);
		head1.left.left = new Node(4);
		head1.left.right = new Node(5);
		head1.right.left = new Node(6);
		head1.right.right = new Node(7);
		head1.left.left.left = new Node(8);
		head1.right.left.right = new Node(9);
		toSequence(head1);
		System.out.println(toSequence(head1));

		printTree(head1);

		String pre = serialByPre(head1);
		System.out.println("serialize tree by pre-order: " + pre);
	}
}
